
//***************************************************************************
//                              Boxtree
//***************************************************************************
//  Copyright (C):
//***************************************************************************
//CVSId: "@(#)$Id$"
//***************************************************************************


#ifndef Boxtree_H
#define Boxtree_H
#if defined(__sgi) || defined(_WIN32)
#pragma once
#endif

//---------------------------------------------------------------------------
//  Includes
//---------------------------------------------------------------------------

#include <limits>
#include <col_import_export.h>
#include <ColGeometry.h>

namespace col {

//---------------------------------------------------------------------------
//  Forward Declarations
//---------------------------------------------------------------------------

struct Data;
struct ElemBox;
struct BoxtreePrecomp;


//***************************************************************************
//  Boxtree
//***************************************************************************

class COL_EXPORTIMPORT Boxtree
{
 public:

	//---------------------------------------------------------------------------
	//  Public Class methods and constants
	//---------------------------------------------------------------------------
	
	/// Max # vertices a boxtree leaf can handle (must be 4)
	static const unsigned int M_MaxNVertices = 4;
	
	/// Max depth of a Boxtree (should never happen)
	static const unsigned int M_MaxDepth = 100;
	
	/** Threshold determining when splitting off an empty box is better.
	 *  This value seems best, at least for torus with 20000 triangles
	 *  and sphere with 20000 triangles.
	 *  @todo
	 *    Warum gibt es immer genau die gleiche Anzahl von "shrink" Nodes,
	 *    egal welchen Wert man hier waehlt? (und trotzdem aendert sich die
	 *    Kollisionszeit signifikant!)
	 **/
    static const REAL M_EmptyGood /*=0.15*/;
    
	/// Flag for distinguishing between leaves and inner nodes
	static const unsigned int M_InnerNode = 0x8000;
	
	//---------------------------------------------------------------------------
	//  Public Instance methods
	//---------------------------------------------------------------------------

	Boxtree( const ColGeometry *geom,
	         vector<const Pnt3Array*> &points,
	         unsigned int maxdepth = M_MaxDepth,
	         REAL emptygood = M_EmptyGood );
	
	virtual ~Boxtree() throw();
	
	bool check( const Boxtree &other,
				const ColGeometry *e_geo, const ColGeometry *f_geo,
				Data *data) const;
	
	typedef enum { PRINT_HUMAN, PRINT_DOT } FormatE;
	
	void printTree( const ColGeometry *geo, FILE *outf = NULL,
					const FormatE format = PRINT_HUMAN ) const;
	
	void stats( const ColGeometry *geo, 
				unsigned int *n_leaves, unsigned int *n_nodes,
				unsigned int *n_shrinks,
				unsigned int *emptyborder, unsigned int emptyb_size,
				unsigned int depthhistogram[M_MaxDepth] ) const;
	
	//---------------------------------------------------------------------------
	//  Instance variables
	//---------------------------------------------------------------------------
	
 protected:
	
	/** X, Y, or Z (0,1,2).
	 *  Could be a single byte, but that does not save memory
	 *  probably because of padding.
	 **/
	unsigned int m_cutplane;
	
    /**
     */
	union
	{
		// Data for inner nodes
		struct
		{
			/** Children.
			 *  m_left = sub-box containing box origin of box.
			 **/
			Boxtree *m_left, *m_right;
			REAL m_cutp;				///< Cut-coord for left sub-box
			REAL m_cutr;				///< Cut-coord for right sub-box
		} ;
		
		// Data for leaves
		struct
		{
			/** Index of the polygon according to the FaceIterator
			 * If the high bit of m_index is set, then the node is a
			 * leaf node and the InnerNode struct must be used.
			 * See BOOST_STATIC_ASSERT in ColBoxtree.cpp .
			 **/
			unsigned int m_index;
			/** The enclosed polygon, if leaf node (indices into vertex array).
			 * If triangle, then pgon[3] == MAX_UINT
			 **/
			unsigned int m_pgon[M_MaxNVertices];
			
			// the dereference of this pointer is initialzed outside.
			// shouldn't deleted by his destructor
			const Pnt3Array *m_points;
		} ;
	};

	//---------------------------------------------------------------------------
	//  Private Instance methods
	//---------------------------------------------------------------------------
	
 protected:
	
	Boxtree( vector<ElemBox> elems[3],
			 const unsigned int in, const unsigned int left, const unsigned int right,
			 const Point3 &low, const Point3 &high,
			 unsigned int depth, REAL emptygood,
			 unsigned int *max_depth_reached,
			 unsigned int *brute_force_splits );
	
	void build( vector<ElemBox> elems[3],
				const unsigned int in, const unsigned int left, const unsigned int right,
				const Point3 &low, const Point3 &high,
				unsigned int depth, REAL emptygood,
				unsigned int *max_depth_reached,
				unsigned int *brute_force_splits );
	
	REAL trySplit( vector<ElemBox> &elem,
				   const int left, const int right,
				   const Point3 &low, const Point3 &high, int coord,
				   REAL *c, REAL *cr, int *splitindex ) const;
	
	bool check( const BoxtreePrecomp &precomp, const Boxtree *other,
			    REAL const *const e, REAL const *const f,
				Data *data ) const;
	
    bool check( const BoxtreePrecomp &precomp, const Boxtree *other,
			    REAL const *const e, REAL const *const f, bool allpolygons,
				Data *data ) const;
	
	void printTree( Point3 low, Point3 high, unsigned int depth,
					FILE *outf, const FormatE format ) const;
	
	void stats( const Point3 &low, const Point3 &high,
				unsigned int *n_leaves, unsigned int *n_nodes,
				unsigned int *n_shrinks,
				unsigned int *emptyborder, unsigned int emptyb_size,
				REAL truevol[6], const Pnt3Array *points,
				unsigned int depthhistogram[M_MaxDepth],
				unsigned int depth ) const;
	
 private:
	
	/// prohibit certain methods
	//~Boxtree() throw();
	Boxtree( const Boxtree &source );
	Boxtree& operator = ( const Boxtree &source );
	bool operator == ( const Boxtree &other ) const;
	bool operator != ( const Boxtree &other ) const;

};

	
//***************************************************************************
//  BoxtreePrecomp
//***************************************************************************

struct COL_EXPORTIMPORT BoxtreePrecomp
{
	/** Three unit vectors spanning the bbox of @a this in @a other's
	 *  coord system in Boxtree::check().
	 **/
	REAL m_b[3][3];
	bool m_b_gt_0[3][3];				///< precomputed REAL comparisons

	BoxtreePrecomp( const Matrix4 &m );
};



//***************************************************************************
//  ElemBox
//***************************************************************************

struct COL_EXPORTIMPORT ElemBox
{
	Point3 m_low, m_high;						// low and high of box

	// the dereference of this pointer is initialzed outside.
	// shouldn't deleted by his destructor
	const Pnt3Array *m_points;

	unsigned int m_pgon[Boxtree::M_MaxNVertices];// vertices of enclosed polygon
	unsigned int m_nvertices;

	unsigned int m_index;						// OSG index of polygon
	Point3 m_center;							// center of polygon

	ElemBox();
	ElemBox( unsigned int index, const Primitive *prim, const Pnt3Array *points );
	void set( unsigned int index, const Primitive *prim, const Pnt3Array *points );
	void operator =  ( const ElemBox &source );
	bool operator == ( const ElemBox &other ) const;

	static
	void calcBox( const vector<ElemBox> &elem, const int left, const int right,
				  Point3 *low, Point3 *high );
};

} // namespace col

#endif /* Boxtree_H */

